package com.demo17_电话号码的字母组合;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        List<String> stringList = letterCombinations("23");
        System.out.println(stringList);
    }

    public static List<String> letterCombinations(String digits) {

        ArrayList<String> list = new ArrayList<>();

        if (digits.length() == 0) {
            return list;
        }
        StringBuilder stringBuilder = new StringBuilder();
        dfs(list, digits, 0, stringBuilder);
        return list;
    }

    /**
     * index 代表的是遍历的字符串中的第几个数字
     * @param list
     * @param digits
     * @param index
     * @param stringBuilder
     */
    private static void dfs(ArrayList<String> list, String digits, int index, StringBuilder stringBuilder) {
        //1.边界条件：  可以是这个每一个收集结果的长度==这个 digits的长度， 或者是 index 到了这个 digits 的下一位~
        if (stringBuilder.toString().length() == digits.length()) {
            list.add(stringBuilder.toString());// 每次调用这个 toString（）都会产生一个新的对象
            return;
        }
        //2.横向遍历: 此处的横向遍历需要通过 index 来控制。 横向遍历 string
        String[] strings = getStrings(String.valueOf(digits.charAt(index)));
        for (int i = 0; i < strings.length; i++) {

            stringBuilder.append(strings[i]);
            //3.纵向递归
            dfs(list, digits, index + 1, stringBuilder);
            //4.回溯
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }

    public static String[] getStrings(String s) {
        switch (s) {
            case "2":
                return new String[]{"a", "b", "c"};
            case "3":
                return new String[]{"d", "e", "f"};
            case "4":
                return new String[]{"g", "h", "i"};
            case "5":
                return new String[]{"j", "k", "l"};
            case "6":
                return new String[]{"m", "n", "o"};
            case "7":
                return new String[]{"p", "q", "r", "s"};
            case "8":
                return new String[]{"t", "u", "v"};
            case "9":
                return new String[]{"w", "x", "y", "z"};
        }
        return null;
    }
}
